package datastructure.maxheap;


/**
 * @author XY
 * @version 1.0
 * @date 2021/8/30 14:54
 * @Description 数据结构-数组
 */
public class Array<E> {

    private E[] data;
    private int size;

    //默认数组长度为10
    public Array(){
        this(10);
    }

    //构造函数设置数组长度
    public Array(int capacity){
        data = (E[]) new Object[capacity];
        size=0;
    }

    public Array(E[] arr){
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i]=arr[i];
        }
        size = arr.length;

    }

    //获取数组中的元素的个数
    public int getSize(){
        return size;
    }

    //获取数组的长度
    public int getCapacity(){
        return data.length;
    }

    public boolean isEmpty(){
        return size==0;
    }

    //向数组的默认添加元素
    public void addLast(E e){
        add1(size,e);
    }

    public void addFirst(E e){
        add1(0,e);
    }

    //在指定位置添加元素，必须保证添加后的数组长度不超过数组定义好的长度
    public void add1(int index,E e){

        if(index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Require index>=0 and index <= size");
        }
        //扩容
        if(size == data.length){
            resize(2 * data.length);
        }
        for(int i=size; i>index; i--){
            data[i]=data[i-1];
        }
        data[index] = e;
        size++;
    }

    //在指定位置添加元素，不考虑超出数组长度
    public void add(int index,E e){

        if(index<0||index>size){
            throw new IllegalArgumentException("Add failed. Require index>=0 and index <= size");
        }
        E[] newArr=(E[])new Object[size+1];
        for (int i = 0; i < size; i++) {
            if(i<index){
                newArr[i]=data[i];
            }
            if(i==index){
                newArr[i]=e;
            }
            if(i>index){
                newArr[i]=data[i-1];
            }
        }
        data=newArr;
        size++;
    }

    //获取数组中index位置的值
    public E get(int index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("Get failed.Index is illegal");
        }
        return data[index];
    }

    //设置数组指定位置的值
    public void set(int index,E e){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("Get failed.Index is illegal");
        }
        data[index] = e;
    }

    //判断数组包含某个元素
    public boolean contains(E e){
        for (int i = 0; i < size; i++) {
            if(data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    //找到元素并返回下标
    public int find(E e){
        for (int i = 0; i < size; i++) {
            if(data[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

    public void delete(int index){
        E[] newArr= (E[])new Object[size-1];
        for (int i = 0; i < size; i++) {
            if(i<index){
                newArr[i]=data[i];
            }
            if(i>index){
                newArr[i-1]=data[i];
            }
        }
        data=newArr;
        size--;
    }

    public void swap (int i ,int j){
        E t = data[i];
        data[i] = data[j];
        data[j]= t;
    }

    public E getLast(){
        return get(size-1);
    }

    public E getFirst(){
        return get(0);
    }

    public E deleteLast(){
        return delete1(size-1);
    }

    public E deleteFirst(){
        return delete1(0);
    }

    //丛数组中删除index位置的元素，返回被删除的元素
    public E delete1(int index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("Delete failed.Index is illegal");
        }
        E ret = data[index];
        for(int i = index+1 ;i<size;i++){
            data[i-1]=data[i];
        }
        size--;
        //这个代码可有可无，loitering objects != memory leak
        data[size] = null;
        if(size == data.length/4 && data.length/2 != 0){
            resize(data.length/2);
        }
        return ret;
    }

    private void resize(int newCapacity){
        E[] newData =(E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i]= data[i];
        }
        data=newData;
    }

    @Override
    public String toString() {
        StringBuilder sb= new StringBuilder();
        sb.append('[');
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if(i!=size-1){
                sb.append(",");
            }
        }
        sb.append(']');
        return sb.toString();
    }
}
